#include<iostream>

#include<assert.h>
using namespace std;

namespace MyList{

  /*单个节点*/
template<class T>
  struct  list_node{
    T _data;
    list_node<T>* _prev;
    list_node<T>* _next;
    
   // list_node(const T&val)//这里应该给缺省值,但是缺省值不能给0
   // 若T是自定义类型,0不能提供相应的初始化,例如string
    list_node(const T&val = T())//这里所给的缺省值为匿名对象,在C++中可以看作内置类型也具有构造函数
   :_prev(nullptr)
    ,_next(nullptr)
    ,_data(val)//这里的T若是为一个自定义类型,则将会去调用它的构造函数
    {}

  };

//////////////////////////////////////////
/* 对迭代器进行封装 */

/*
 * 这里添加了一个模板参数Ref，
 * 该模板参数可以确保在调用过程中所使用的迭代器
 * 为普通迭代器还是const迭代器
 * 在总体框架中将__list_iterator<T,T&>与
 * __list_iterator<T,const T&>进行typedef为iterator与const_iterator
 * 但是在实际的实例化中,两个不同的模板参数构造出两个不同的类(重点)
  */
template<class T,class Ref,class Ptr>
struct __list_iterator{
  typedef list_node<T> node;
  typedef __list_iterator<T , Ref , Ptr> self;
  node* _node;

  __list_iterator(node* n)
   : _node(n)//只有一个参数且为指针
  {}

  Ptr operator->(){
    /*
     * 若是为自定义类型的话,这里将& 自定义类型对象的指针
     * 在使用中,原来应该 it->->进行调用
     * (第一个->为调用operator->,第二个->为调用后找到该地址并使用
     * ->进行数据的访问)
     * 但是在这里编译器进行了优化,将两个->省略了一个,
     * 以此达到一个->即可进行访问数据
     */
    return &_node->_data;
  }


  //重载使迭代器能够达到解引用的效果
  Ref operator*(){
    return _node->_data;
  }

  //前置++重载，使得迭代器能够像string和vector一样能够方便的进行++
  self& operator++(){
    _node = _node->_next;
    return *this;
  }
  
  self operator++(int){
    self ret(*this);
    _node = _node->_next;
    return ret;
  }

  self& operator--(){
    _node = _node->_prev;
    return *this;
  }
  
  self operator--(int){
    self ret(*this);
    _node = _node->_prev;
    return ret;
  }
  //!=重载，使得该符号能够实现根据end来进行遍历
  bool operator!=(const self&s){
    return _node!=s._node;
  }


  bool operator==(const self&s){
    return _node==s._node;
  }

};

/*
 * 1.迭代器要么就是原生指针
 * 2.迭代器要么就是自定义类型对原生指针的封装,模拟指针的行为
 * */

//////////////////////////////////////////

  /*整体list框架*/
template<class T>
  class list{
    typedef list_node<T> node;

  public:

     typedef __list_iterator<T , T& , T*> iterator;
     typedef __list_iterator<T , const T& , const T*> const_iterator;

     void empty_init(){//空初始化
       _head = new node;//这里也会去调用对应的构造函数
       _head->_prev = _head->_next = _head;
     }

     template<class Iterator>//所传的迭代器不一定是同一种迭代器，所以要
       //用模板参数
       list(Iterator first,Iterator last){
         /*
          * 迭代器区间构造
          */
         empty_init();
         while(first != last){
           push_back(*first);
           ++first;
         }
       }

     void swap(list<T>& tmp){
       std::swap(_head,tmp._head);
     }

     /*
     list(const list<T>& tmp){
        empty_init();
        for(const auto& it : tmp){
          push_back(it);
        }
     } //传统写法
      */

     //现代写法
     list(const list<T>& lt){
       empty_init();
       list<T> tmp(lt.begin(),lt.end());
       swap(tmp);
     }

     list()//构造函数
     {
      empty_init();
     }

     ~list()
     {
      empty_init();
       clear();
       delete[]_head;
       _head = nullptr;
     }

     void push_back(const T&val){
      /* node*tail = _head->_prev;
       node*new_node =  new node(val);//根据参数调用对应的构造函数
      
       tail->_next = new_node;
       new_node->_prev = tail;
       _head->_prev = new_node;
       new_node->_next = _head;*/

      //存在insert后复用即可
      insert(end(),val);

     }

     void push_front(const T& val){
      //同样进行复用insert  
        insert(begin(),val);
     }


     void insert(iterator pos , const T& x){
      //通过迭代器转换为原指针即可
       node* cur = pos._node;//当前节点的指针
       node* prev = cur->_prev;//上一个节点的指针

       node* new_node = new node(x);
       prev->_next = new_node;
       new_node->_prev = prev;

       cur->_prev = new_node;
       new_node->_next = cur;

     }

     void clear(){
        iterator it = begin();
        while(it!=end()){
          it = erase(it);
        }

     }

     iterator erase(iterator pos){
     //该函数需要返回一个当前被删除的节点的下一个节点 
       assert(pos != end());
        node* cur = pos._node; 
        node* prev = cur -> _prev;
        node* next = cur -> _next;

        prev -> _next = next;
        next -> _prev = prev;

       delete cur; 

       return iterator(next);
     }

     list<T>& operator=(list<T> it){
       swap(it);
       return *this;
     }

     void pop_back(){

       erase(--end());
     }
     void pop_front(){

       erase(begin());
     }





    iterator begin()
    {
      return iterator(_head->_next);
    }

    iterator end()
    {
      return iterator(_head);
    }
  
    const_iterator begin() const
    {
      return const_iterator(_head->_next);
    }

    const_iterator end() const
    {
      return const_iterator(_head);
    }
  private:
    node* _head;//哨兵位头节点
  };









}
